2012年信息学奥赛NOIP普及组
初赛
更早
2023-08-21 20:52:15
125次
一、单选题
二、填空题
#include <iostream>
using namespace std;
int n, i,j, a[100][100];
int solve(int x, inty)
{
int u, v;
if (x == n)
return a[x][y];
u = solve(x + 1, y);
v = solve(x + 1, y + 1);
if (u > v)
return a[x][y] + u;
else
return a[x][y] + v;
}
int main()
{
cin>>n;
for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++)
cin>>a[i][j];
cout<<solve(1, 1)<<endl;
return 0;
}输入 :
5
2
-1 4
2 -1 -2
-1 6 4 0
3 2 -1 5 8
输出：
【知识点】 信息学NOIP普及组
#include <iostream>
#include <string>
using namespace std;
int n, ans, i, j;
string s;
charget(inti)
{
if (i < n)
return s[i];
else
return s[i-n];
}
int main()
{
cin>>s;
n = s.size();
ans = 0;
for (i = 1; i <= n-1; i++)
{
for (j = 0; j <= n-1; j++) if (get(i+j) < get(ans+j))
{
ans = i;
break;
}
else if (get(i+j) > get(ans+j))
break;
}
for (j = 0; j <= n-1; j++)
cout<<get(ans+j);
cout<<endl;
}输入： CBBADADA
输出：
【知识点】 信息学NOIP普及组
三、简答题
完善程序：（排列数）输入两个正整数n, m (1 ≤n ≤20, 1 ≤m ≤n)，在 1~n 中任取 m 个数，按字典序从小到大输出所有这样的排列。例如
输入
3 2
输出：
1 2 1 3 2 1 2 3 3 1 3 2
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 25;
bool used[SIZE];
int data[SIZE];
int n, m, i,j, k;
bool flag;
int main()
{
cin>>n>>m;
memset(used, false, sizeof(used));
for (i = 1; i <= m; i++)
{
data[i] = i;
used[i] = true;
}
flag = true;
while (flag)
{
for (i = 1; i <= m-1; i++) cout<<data[i]<<" ";
cout<<data[m]<<endl;
flag = ① ;
for (i = m; i >= 1; i--)
{
② ;
for (j = data[i]+1; j <= n; j++) if (!used[j])
{
used[j] = true;
data[i] = ③ ;
flag = true;
break;
}
if (flag)
{
for (k = i+1; k <= m; k++)
for (j = 1; j <= ④ ; j++) if (!used[j])
{
data[k] = j;
used[j] = true;
break;
}
⑤ ;
}
}
}
}
【知识点】 信息学NOIP普及组
完善程序：坐标统计
输入 n 个整点在平面上的坐标。 对于每个点，可以控制所有位于它左下方的点（即 x 、y 坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果两个点战斗力一样， 输出较大的编号）。
#include<iostream>
using namespace std;
const int SIZE = 100;
intx[SIZE], y[SIZE], f[SIZE];
int n, i,j, max_f, ans;
int main()
{
cin>>n;
for (i = 1; i <= n; i++)
cin>>x[i]>>y[i];
max_f = 0;
for (i = 1; i <= n; i++)
{
f[i] = ① ;
for (j = 1; j <= n; j++)
{
if (x[j] < x[i] && ② )
③
}
if ( ④ )
{
max_f = f[i];
⑤ ;
}
}
for (i = 1; i <= n; i++)
cout<<f[i]<<endl;
cout<<ans<<endl;
}
【知识点】 信息学NOIP普及组
